package stat;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

/**
 * track component in "newEdges4activeUsers.txt"
 * @author D
 *
 */

public class IdComponent {
	//total user: 1131721/1131712
	private static int[] node_set = new int[1131713];//[1131722];
	
	private static void initial() {
		for (int i = 0; i < node_set.length; i++)
			node_set[i] = i;
	}
	
	private static void process(String str) {
		String[] token = str.split("\t");
		procNewEdge(Integer.parseInt(token[0]), Integer.parseInt(token[1]));
	}
	
	private static void procNewEdge(int x, int y) {
		int root_x = getRoot(x);
		int root_y = getRoot(y);
		int root_xy = root_x < root_y ? root_x : root_y;
		node_set[x] = root_xy;
		node_set[y] = root_xy;
		node_set[root_x] = root_xy;
		node_set[root_y] = root_xy;
	}
	
	private static int getRoot(int i) {
		int root = node_set[i];
		while (node_set[root] != root)
			root = node_set[root];		
		return root;
	}
	
	private static int son2brother() {
		int count = 0;
		for (int i = 0; i < node_set.length; i++) {
			if (node_set[i] != getRoot(i)) {
				node_set[i] = getRoot(i);
				count++;
			}
		}
		return count;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		initial();
		
		String dataPath = "/home/ddxu/data/newEdges4activeUsers2.txt";
		String resultPath = "/home/ddxu/data/newComponentSets2.txt";
		
		try {
			BufferedReader in = new BufferedReader(new FileReader(dataPath));
			String str;
			while ((str = in.readLine()) != null) {
				process(str);
			}
			
			in.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
		
		int count;
		do {
			count = son2brother();
			System.out.println(count);
		} while (count != 0);
		
		try {
			BufferedWriter out = new BufferedWriter(new FileWriter(resultPath));
			for (int i = 1; i < node_set.length; i++) {
				out.write(Integer.toString(i) + "\t" + Integer.toString(node_set[i]));
				out.newLine();
			}
			out.flush();
			out.close();
		} catch (IOException e) {
			e.printStackTrace();
		}

	}

}
